home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / program / ddj0897.zip / DYN401.ZIP / class / btreenod.d < prev    next >
Text File  |  1996-08-19  |  11KB  |  494 lines
  1.  
  2.  
  3.  
  4. /*                                      
  5.  *
  6.  *      Copyright (c) 1993-1996 Algorithms Corporation
  7.  *      3020 Liberty Hills Drive
  8.  *      Franklin, TN 37067
  9.  *
  10.  *      ALL RIGHTS RESERVED.
  11.  *
  12.  *      
  13.  *      
  14.  */
  15.  
  16.  
  17.  
  18. #include <string.h>
  19.  
  20. #define    OBJECTS_PER_NODE    50
  21.  
  22. #define    MAX_DEPTH        10
  23.  
  24.  
  25. #define    MEMMOVE(a,b,c)    memmove((void *)(a), (void *)(b), c)
  26. #define    MEMSET(a,b,c)    memset((void *)(a), b, c)
  27. #define    MEMCPY(a,b,c)    memcpy((void *)(a), (void *)(b), c)
  28.  
  29. defclass  BTreeNode {
  30.     int    iUsed;                //  number of used iKeys
  31.     int    iType;                //  1=intermediate, 2=leaf
  32.     iKeys[OBJECTS_PER_NODE];
  33.     iObjects[OBJECTS_PER_NODE+1];        //  data or intermediate nodes
  34.  
  35.  
  36.     iBTree;                    //  BTree instance
  37.     iPrevious;                //  previous node (only used as temporary during processing)
  38.                                             //  creates a linked list up the chain
  39. class:
  40.     cData;                    //  just some constant to be used as default data
  41. };
  42.  
  43.  
  44. cmeth    gNewNode(btree, int type)
  45. {
  46.     object    obj = gNew(super);
  47.     accessIVsOf(obj);
  48.     iBTree = btree;
  49.     iType = type;
  50.     if (!cData)
  51.         cData = gNew(Constant);
  52.     return obj;
  53. }
  54.  
  55. imeth    gDispose()
  56. {
  57.     int    i;
  58.     object    n;
  59.  
  60.     if (iType == 1) {
  61.         for (i=0 ; i < iUsed ; ++i) {
  62.             if (n = iKeys[i])
  63.                 gDeepDispose(n);
  64.             if (n = iObjects[i])
  65.                 gDispose(n);
  66.         }
  67.         if (n = iObjects[iUsed])
  68.             gDispose(n);
  69.     }
  70.     return gDispose(super);
  71. }
  72.  
  73. imeth    gDeepDispose()
  74. {
  75.     int    i;
  76.     object    n;
  77.  
  78.     for (i=0 ; i < iUsed ; ++i) {
  79.         if (n = iKeys[i])
  80.             gDeepDispose(n);
  81.         if (n = iObjects[i])
  82.             gDeepDispose(n);
  83.     }
  84.     if (iType == 1  &&  (n = iObjects[iUsed]))
  85.         gDeepDispose(n);
  86.     return gDispose(super);
  87. }
  88.  
  89. static    int    bsearch2(ivType *iv, ifun cfun, object key, int *idx)
  90. {
  91.     int    low = 0, high = iUsed-1, mid, cond;
  92.  
  93.     while (low <= high) {
  94.         mid = (low + high) / 2;
  95.         cond = cfun(key, iKeys[mid]);
  96.         if (cond < 0)
  97.             high = mid - 1;
  98.         else if (cond > 0)
  99.             low = mid + 1;
  100.         else 
  101.             break;
  102.     }
  103.     if (low <= high) {    //  found
  104.         *idx = mid;
  105.         return 1;
  106.     } else {
  107.         *idx = low;
  108.         return 0;
  109.     }
  110. }
  111.  
  112. imeth    gFindBTNEQ : find (ifun cfun, key, object *foundKey)
  113. {
  114.     int    found, idx;
  115.  
  116.     found = bsearch2(iv, cfun, key, &idx);
  117.     if (iType == 2)
  118.         if (found) {
  119.             if (foundKey)
  120.                 *foundKey = iKeys[idx];
  121.             return iObjects[idx];
  122.         } else
  123.             return NULL;
  124.     return find(iObjects[found+idx], cfun, key, foundKey);
  125. }
  126.  
  127. imeth    gFindBTNFirst : findFirst (ifun cfun, object *foundKey)
  128. {
  129.     if (iType == 2) {
  130.         if (foundKey)
  131.             *foundKey = iKeys[0];
  132.         return iObjects[0];
  133.     }
  134.     return findFirst(iObjects[0], cfun, foundKey);
  135. }
  136.  
  137. imeth    gFindBTNLast : findLast (ifun cfun, object *foundKey)
  138. {
  139.     if (iType == 2) {
  140.         if (foundKey)
  141.             *foundKey = iKeys[iUsed-1];
  142.         return iObjects[iUsed-1];
  143.     }
  144.     return findLast(iObjects[iUsed], cfun, foundKey);
  145. }
  146.  
  147. imeth    gFindBTNGE : findGE (ifun cfun, object key, object *foundKey)
  148. {
  149.     int    found, idx;
  150.     object    ret;
  151.  
  152.     found = bsearch2(iv, cfun, key, &idx);
  153.     if (iType == 2)
  154.         if (idx != iUsed) {
  155.             if (foundKey)
  156.                 *foundKey = iKeys[idx];
  157.             return iObjects[idx];
  158.         } else {
  159.             if (foundKey)
  160.                 *foundKey = NULL;
  161.             return NULL;
  162.         }
  163.     for (idx=idx+found ; idx <= iUsed ; idx++)
  164.         if (ret = findGE(iObjects[idx], cfun, key, foundKey))
  165.             return ret;
  166.     return NULL;
  167. }
  168.  
  169. imeth    gFindBTNGT : findGT (ifun cfun, object key, object *foundKey)
  170. {
  171.     int    found, idx;
  172.     object    ret;
  173.  
  174.     found = bsearch2(iv, cfun, key, &idx);
  175.     if (found)
  176.         idx++;
  177.     if (iType == 2)
  178.         if (idx != iUsed) {
  179.             if (foundKey)
  180.                 *foundKey = iKeys[idx];
  181.             return iObjects[idx];
  182.         } else {
  183.             if (foundKey)
  184.                 *foundKey = NULL;
  185.             return NULL;
  186.         }
  187.     for ( ; idx <= iUsed ; idx++)
  188.         if (ret = findGT(iObjects[idx], cfun, key, foundKey))
  189.             return ret;
  190.     return NULL;
  191. }
  192.  
  193. imeth    gFindBTNLE : findLE (ifun cfun, object key, object *foundKey)
  194. {
  195.     int    found, idx;
  196.     object    ret;
  197.  
  198.     found = bsearch2(iv, cfun, key, &idx);
  199.     if (iType == 2)
  200.         if (found) {
  201.             if (foundKey)
  202.                 *foundKey = iKeys[idx];
  203.             return iObjects[idx];
  204.         } else if (idx) {
  205.             if (foundKey)
  206.                 *foundKey = iKeys[idx-1];
  207.             return iObjects[idx-1];
  208.         } else {
  209.             if (foundKey)
  210.                 *foundKey = NULL;
  211.             return NULL;
  212.         }
  213.     for (idx=idx+found ; idx >= 0 ; idx--)
  214.         if (ret = findLE(iObjects[idx], cfun, key, foundKey))
  215.             return ret;
  216.     return NULL;
  217. }
  218.  
  219. imeth    gFindBTNLT : findLT (ifun cfun, object key, object *foundKey)
  220. {
  221.     int    idx;
  222.     object    ret;
  223.  
  224.     bsearch2(iv, cfun, key, &idx);
  225.     if (iType == 2)
  226.         if (idx) {
  227.             if (foundKey)
  228.                 *foundKey = iKeys[idx-1];
  229.             return iObjects[idx-1];
  230.         } else {
  231.             if (foundKey)
  232.                 *foundKey = NULL;
  233.             return NULL;
  234.         }
  235.     for ( ; idx >= 0 ; idx--)
  236.         if (ret = findLT(iObjects[idx], cfun, key, foundKey))
  237.             return ret;
  238.     return NULL;
  239. }
  240.  
  241. static    void    collapse(ivType *liv, object lo, int deep)
  242. {
  243.     object    self = liv->iPrevious;
  244.     ivType    *iv = ivPtr(self);
  245.     int    idx;
  246.  
  247.     if (iUsed == 1)
  248.         if (iPrevious) {
  249.             collapse(iv, liv->iPrevious, deep);
  250.             return;
  251.         } else if (iType == 1) {
  252.             if (deep)
  253.                 gDeepDispose(lo);
  254.             else
  255.                 gDispose(lo);
  256.             iKeys[0] = gDeepDispose(iKeys[0]);
  257.             gSetTopNode(iBTree, iObjects[iObjects[0] == lo]);
  258.             iObjects[0] = iObjects[1] = NULL;
  259.             iUsed = 0;
  260.             gDeepDispose(self);
  261.             return;
  262.         }
  263.     for (idx=0 ; iObjects[idx] != lo ; idx++);
  264.     if (!idx) {
  265.         gDeepDispose(iKeys[0]);
  266.         MEMMOVE(iKeys, iKeys+1, (iUsed-1)*sizeof(object));
  267.         MEMMOVE(iObjects, iObjects+1, iUsed*sizeof(object));
  268.     } else {
  269.         gDeepDispose(iKeys[idx-1]);
  270.         MEMMOVE(iKeys+idx-1, iKeys+idx, (iUsed-idx)*sizeof(object));
  271.         MEMMOVE(iObjects+idx, iObjects+idx+1, (iUsed-idx)*sizeof(object));
  272.     }
  273.     iKeys[iUsed-1] = iObjects[iUsed] = NULL;
  274.     iUsed--;
  275.     if (deep)
  276.         gDeepDispose(lo);
  277.     else
  278.         gDispose(lo);
  279. }
  280.  
  281. imeth    gDeleteBTNode : delete (ifun cfun, key, int deep, prev)
  282. {
  283.     int    found, idx;
  284.     object    res;
  285.  
  286.     found = bsearch2(iv, cfun, key, &idx);
  287.     if (iType == 2) {
  288.         if (!found)
  289.             return NULL;
  290.         if (iUsed == 1  &&  prev) {
  291.             iPrevious = prev;
  292.             collapse(iv, self, deep);
  293.         } else {
  294.             int    n = iUsed - idx - 1;
  295.             if (deep) {
  296.                 gDeepDispose(iKeys[idx]);
  297.                 gDeepDispose(iObjects[idx]);
  298.             }
  299.             MEMMOVE(iKeys+idx, iKeys+idx+1, n*sizeof(object));
  300.             MEMMOVE(iObjects+idx, iObjects+idx+1, n*sizeof(object));
  301.             iUsed--;
  302.             iKeys[iUsed] = iObjects[iUsed] = NULL;
  303.         }
  304.         return self;
  305.     }
  306.     iPrevious = prev;
  307.     res = delete(iObjects[found+idx], cfun, key, deep, self);
  308.     iPrevious = NULL;
  309.     return res;
  310. }
  311.  
  312. static    object    split(object lo, ivType *left, ifun cfun)
  313. {
  314.     object    to, ro, ret;
  315.      ivType    *right, *top;
  316.     int    lhalf, rhalf;
  317.  
  318.     ro = gNewNode(CLASS, left->iBTree, left->iType);
  319.      right = ivPtr(ro);
  320.     if (left->iType == 2) {
  321.         lhalf = left->iUsed / 2;
  322.         rhalf = left->iUsed - lhalf;
  323.         MEMCPY(right->iKeys, left->iKeys+lhalf, rhalf*sizeof(object));
  324.         MEMSET(left->iKeys+lhalf, 0, rhalf*sizeof(object));
  325.         left->iUsed = lhalf;
  326.         right->iUsed = rhalf;
  327.         MEMCPY(right->iObjects, left->iObjects+lhalf, rhalf*sizeof(object));
  328.         MEMSET(left->iObjects+lhalf, 0, rhalf*sizeof(object));
  329.     } else {
  330.         lhalf = left->iUsed / 2;
  331.         rhalf = left->iUsed - lhalf - 1;
  332.         MEMCPY(right->iKeys, left->iKeys+lhalf+1, rhalf*sizeof(object));
  333.         MEMSET(left->iKeys+lhalf+1, 0, rhalf*sizeof(object));
  334.         left->iUsed = lhalf;
  335.         right->iUsed = rhalf;
  336.         MEMCPY(right->iObjects, left->iObjects+lhalf+1, (rhalf+1)*sizeof(object));
  337.         MEMSET(left->iObjects+lhalf+1, 0, (rhalf+1)*sizeof(object));
  338.     }
  339.  
  340.     if (!(ret=to=left->iPrevious)) {
  341.         ret = to = gNewNode(CLASS, left->iBTree, 1);
  342.         gSetTopNode(left->iBTree, to);
  343.         top = ivPtr(to);
  344.         top->iKeys[0] = gDeepCopy(right->iKeys[0]);
  345.         top->iObjects[0] = lo;
  346.         top->iObjects[1] = ro;
  347.         top->iUsed = 1;
  348.     } else {
  349.         int    found, idx, n;
  350.  
  351.         top = ivPtr(to);
  352.         if (top->iUsed == OBJECTS_PER_NODE) {
  353.             ret = to = split(to, top, cfun);
  354.             top = ivPtr(to);
  355.             found = bsearch2(top, cfun, right->iKeys[0], &idx);
  356.             to = top->iObjects[found+idx];
  357.             top = ivPtr(to);
  358.         }
  359.         found = bsearch2(top, cfun, right->iKeys[0], &idx);
  360.         if (found)
  361.             gError(Dynace, "BTreeNode error");
  362.         n = top->iUsed - idx;
  363.         if (n) {
  364.             MEMMOVE(top->iKeys+idx+1, top->iKeys+idx, n*sizeof(object));
  365.             MEMMOVE(top->iObjects+idx+2, top->iObjects+idx+1, n*sizeof(object));
  366.         }
  367.         top->iKeys[idx] = gDeepCopy(right->iKeys[0]);
  368.         top->iObjects[idx+1] = ro;
  369.         top->iUsed++;
  370.     }
  371.  
  372.     return ret;
  373. }
  374.  
  375. /*
  376.   cfun        key comparison function (args like strcmp)
  377.   key        key used for comparisons
  378.   data        data to be associated with key
  379.   replace    if key already found 0=don't replace, 1=replace
  380.   replaced    0=dup found and not replaced, 1=new key added, 2=dup key found and data replaced - key not used
  381.   prev        previous not in search path
  382.   old        old data (if dup key found and data replaced)
  383. */
  384.  
  385. #define    DATA    data ? data : cData
  386.  
  387. imeth    gAddBTreeNode : add (ifun cfun, key, data, int replace, int *replaced, prev, object *old)
  388. {
  389.     int    found, idx;
  390.     object    tmp,  ret;
  391.  
  392.     found = bsearch2(iv, cfun, key, &idx);
  393.     if (iType == 1) {
  394.         iPrevious = prev;
  395.         ret = add(iObjects[found+idx], cfun, key, DATA, replace, replaced, self, old);
  396.         iPrevious = NULL;
  397.         return ret;
  398.     }
  399.  
  400.     if (found)            //  already exists
  401.         if (replace) {
  402.             *old = iObjects[idx];
  403.             iObjects[idx] = DATA;
  404.             *replaced = 2;
  405.             return self;
  406.         } else {
  407.             *replaced = 0;
  408.             return self;
  409.         }
  410.  
  411.     //  node doesn't already exist - insert
  412.  
  413.     if (iUsed == OBJECTS_PER_NODE) {    //  node full
  414.         iPrevious = prev;
  415.         tmp = split(self, iv, cfun);
  416.         iPrevious = NULL;
  417.         return add(tmp, cfun, key, DATA, replace, replaced, NULL, old);
  418.     }
  419.  
  420.     if (idx != iUsed) {             //  not append
  421.         int    n = iUsed - idx;
  422.         MEMMOVE(iKeys+idx+1, iKeys+idx, n*sizeof(object));
  423.         MEMMOVE(iObjects+idx+1, iObjects+idx, n*sizeof(object));
  424.     }
  425.     iKeys[idx] = key;
  426.     iObjects[idx] = DATA;
  427.     iUsed++;
  428.     *replaced = 1;
  429.     return self;
  430. }
  431.  
  432. imeth    gPrint(stream)
  433. {
  434.     int    i, n;
  435.  
  436.     gPrintValue(self, stream);
  437.     gPuts(stream, "\n------------------------------------------------------------\n");
  438.     if (iType == 1) {
  439.         n = iUsed + 1;
  440.         for (i=0 ; i < n ; i++)
  441.             gPrint(iObjects[i], stream);
  442.     }
  443.     return self;
  444. }
  445.  
  446. imeth    gPrintValue(stream)
  447. {
  448.     int    i, n;
  449.     object    t;
  450.     
  451.     vPrintf(stream, "BTree %8.8lx, %s node %8.8lx, %d used\n", iBTree, iType == 1 ? "Intermediate" : "Leaf", self, iUsed);
  452.     if (!iBTree)
  453.         vPrintf(stream, "ERROR: iBTRee not set\n");
  454.     if (iPrevious)
  455.         vPrintf(stream, "ERROR: iPrevious set\n");
  456.     for (i=0 ; i < iUsed ; i++) {
  457.         t = gStringRepValue(iKeys[i]);
  458.         vPrintf(stream, "%s  ", gStringValue(t));
  459.         gDispose(t);
  460.     }
  461.     for ( ; i < OBJECTS_PER_NODE ; i++)
  462.         if (iKeys[i])
  463.             vPrintf(stream, "\nERROR:  iKeys[%d] has an unexpected value.\n", i);
  464.     gPuts(stream, "\n");
  465.     if (iType == 1) {
  466.         n = iUsed + 1;
  467.         for (i=0 ; i < n ; i++)
  468.             vPrintf(stream, "%8.8lx  ", iObjects[i]);
  469.     } else
  470.         for (i=0 ; i < iUsed ; i++) {
  471.             t = gStringRepValue(iObjects[i]);
  472.             vPrintf(stream, "%s  ", gStringValue(t));
  473.             gDispose(t);
  474.         }
  475.     for ( ; i <= OBJECTS_PER_NODE ; i++)
  476.         if (iObjects[i])
  477.             vPrintf(stream, "\nERROR:  iObjects[%d] has an unexpected value.\n", i);
  478.     gPuts(stream, "\n");
  479.     return self;
  480. }
  481.  
  482.  
  483. /*                                      
  484.  *
  485.  *      Copyright (c) 1993-1996 Algorithms Corporation
  486.  *      3020 Liberty Hills Drive
  487.  *      Franklin, TN 37067
  488.  *
  489.  *      ALL RIGHTS RESERVED.
  490.  *
  491.  *      
  492.  *      
  493.  */
  494.